//540 有序数组中的单一元素
/*
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数

输入: [1,1,2,3,3,4,4,8,8]
输出: 2

输入: [3,3,7,7,10,11,11]
输出: 10
*/
class Solution
{
public:
	int singleNonDuplicate(vector<int> &nums)
	{
		int lo = 0;
		int hi = nums.size() - 1;
		while (lo < hi)
		{
			int mid = lo + (hi - lo) / 2;
			bool halvesAreEven = (hi - mid) % 2 == 0;
			if (nums[mid + 1] == nums[mid])
			{
				if (halvesAreEven)
				{
					lo = mid + 2;
				}
				else
				{
					hi = mid - 1;
				}
			}
			else if (nums[mid - 1] == nums[mid])
			{
				if (halvesAreEven)
				{
					hi = mid - 2;
				}
				else
				{
					lo = mid + 1;
				}
			}
			else
			{
				return nums[mid];
			}
		}
		return nums[lo];
	}
};
